//
// Created by (xueliang2007@qq.com):snow on 19-3-29.
//
#include "include/SortMethods.h"
#include<iostream>

/*辅助输出数组*/
template <typename T>
void showArray(T *a, int size)
{
    for (int k = 0; k < size; ++k)
        std::cout<<"  "<<a[k];
    std::cout<<std::endl;
}

/*选择排续*/
void selectSort(int *a, int size)
{
    std::cout<<0<<"\t";
    showArray(a, size);

    for (int i = 0; i < size-1; ++i) {
        //j每次循环一次,就选出剩余部分中最小的一个到次左边
        std::cout<<i+1<<"\t";
        int n = i;
        for (int j = i+1; j < size; ++j) {
            if (a[n] > a[j])
                n = j;
        }

        //相对冒泡排序来说,交换次数较小
        if (n != i)
            std::swap(a[n], a[i]);

        showArray(a, size);
    }
    std::cout<<std::endl;
}

/*冒泡排续*/
void bubbleSort(int *a, int size)
{
    std::cout<<0<<"\t";
    showArray(a, size);

    for (int i = 0; i < size-1; i++) {
        //j每次循环一次,就交换相邻的两个字符
        int isTerminal = 0;
        for (int j = 0; j < size-1; j++) {
            if (a[j] > a[j+1]){
                std::swap(a[j], a[j+1]);
                isTerminal++;
            }
        }

        //在i<size-1时,如果序列两两比较时已经是有序,\
        // 没有发生过交换,则无需对i后续的遍历
        if (!isTerminal)
            break;

        std::cout<<i+1<<"\t";
        showArray(a, size);
    }
    std::cout<<std::endl;
}

/*插入排续*/
void insertSort(int *a, int size)
{
    std::cout<<0<<"\t";
    showArray(a, size);
    int count1 = 0;
    for (int i = 1; i < size; i++) {
        std::cout<<i<<"\t";
        for (int j = i-1; j>=0; j--) {
            if (a[j+1] < a[j])
                std::swap(a[j+1], a[j]);
            else
                break;  //j-1之前已经是有序的了,所以这时候直接break就可以了,能够节省比较次数
            count1++;
        }

        showArray(a, size);
    }
    std::cout<<count1<<std::endl;
}

/*希尔排续*/
void shellSort(int *a, int size)
{
    std::cout<<0<<"\t";
    showArray(a, size);

    int gap = size;
    do{
        gap = gap/3+1;
        for (int i = gap; i < size; i++) {
            for (int j = i-gap; j >= 0 ; j-=gap) {
                if (a[j+gap] < a[j])
                    std::swap(a[j+gap], a[j]);
            }
        }
    }while (gap > 1);

    showArray(a, size);
}

/*归并排续*/
mergeSort::mergeSort(int* a, int size)
{
        if (size > 1){
            int *list1 = a;
            int size1 = size / 2;
            int *list2 = a + size / 2;
            int size2 = size - size1;

            mergeSort(list1, size1);
            mergeSort(list2, size2);

            merging(list1, size1, list2, size2, size);
        }
    }

void mergeSort::merging(int *list1, int size1, int* list2, int size2, const int K_MAX_SIZE)
{
    int i,j,k;
    i=j=k=0;
    int temp[K_MAX_SIZE];
    while (i < size1 && j < size2){
        if (list1[i] < list2[j]){
            temp[k++] = list1[i++];
        } else{
            temp[k++] = list2[j++];
        }
    }
    while (i < size1){
        temp[k++] = list1[i++];
    }
    while (j < size2){
        temp[k++] = list2[j++];
    }

    for (int m = 0; m < (size1+size2); ++m) {
        list1[m] = temp[m];
    }
}

/*堆排序*/
heapSort::heapSort(int *a, int size)
{
    //构建堆
    for (int i = size/2-1; i >= 0; i--) {
        heapJust(a, i, size-1);
    }

    //不断的将堆顶的值和末尾交换,并且重新构建大顶堆
    for (int i = size-1; i > 0; i--) {
        std::swap(a[0], a[i]);
        heapJust(a, 0, i-1);
    }
}

void heapSort::heapJust(int *a, int s, int n) //s是树的第s层
{
    int top = a[s];
    for (int i = s*2+1; i <= n; ) {
        if ((i < n) && (a[i] < a[i+1]))     //(i<n)是因为当i=n的时候,没有i++了
            i++;
        if (top < a[i]){
            a[s] = a[i];    //最大值始终给a[s]
            s = i;          //更新当前层的索引
            i = 2*i+1;      //
        }else
            break;
    }
    a[s] = top;
}

/*快速排序*/
quickSort::quickSort(int* a, int size)
{
    qsort(a, 0, size-1);
}

void quickSort::qsort(int* a, int low, int high)
{
    int point;
    if (low < high){
        point = Partition(a, low, high);

        qsort(a, low, point-1);
        qsort(a, point+1, high);
    }
}

int quickSort::Partition(int* a, int low, int high)
{
    int point;
    point = a[low];
    while (low < high){
        while (low < high && a[high] >= point){ //>= 而不是>
            high--;
        }
        std::swap(a[low], a[high]);

        while (low < high && a[low] <= point){  //<= 而不是<
            low++;
        }
        std::swap(a[low], a[high]);
    }
    return low;
}
